package listnode.data;

import java.util.Random;

public class GenerateRandomListNode {
    // 生成可能存在环的链表
    public static ListNode generateListWithPossibleCycle(int length, int minValue, int maxValue) {
        if (length <= 0) {
            return null;
        }
        Random random = new Random();
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        ListNode[] nodes = new ListNode[length];

        for (int i = 0; i < length; i++) {
            int randomValue = random.nextInt(maxValue - minValue + 1) + minValue;
            current.next = new ListNode(randomValue);
            nodes[i] = current.next;
            current = current.next;
        }

        // 随机决定是否创建环
        if (length > 1 && random.nextBoolean()) {
            int pos = random.nextInt(length);
            current.next = nodes[pos];
        }

        return dummy.next;
    }

    // 生成正常无环的链表
    public static ListNode generateAcyclicList(int length, int minValue, int maxValue) {
        if (length <= 0) {
            return null;
        }
        Random random = new Random();
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        for (int i = 0; i < length; i++) {
            int randomValue = random.nextInt(maxValue - minValue + 1) + minValue;
            current.next = new ListNode(randomValue);
            current = current.next;
        }

        return dummy.next;
    }

    public static void printListNode(ListNode head) {
        if (head == null) {
            System.out.println("null");
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;

        // 检测是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        if (hasCycle) {
            // 找到环的入口
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            ListNode cycleStart = slow;

            // 打印无环部分
            slow = head;
            while (slow != cycleStart) {
                System.out.print(slow.val + " -> ");
                slow = slow.next;
            }
            // 打印环部分
            System.out.print("(cycle starts at " + cycleStart.val + ") ");
            ListNode temp = cycleStart.next;
            while (temp != cycleStart) {
                System.out.print(temp.val + " -> ");
                temp = temp.next;
            }
            System.out.println(cycleStart.val + " (cycle end)");
        } else {
            // 无环链表直接打印
            ListNode current = head;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println();
        }
    }

}